Self-routing packet switching networks such as those using unbuffered banyan switching nodes communicate packets through the switching network on the basis of address information transmitted through the switching network prior to the transmission of the packet. Such a switching network has only one unique path between each input and output pair of the network and is illustrated in FIG. 1. Since circuit switching requires a path to remain setup for an indefinite period of time, information cannot be readily circuit switched through a prior art banyan network because a large portion of the paths would become blocked. Furthermore, such prior art networks were constrained by network protocol requirements to the communication of packets. Whereas packet switching is capable of communicating voice and low to medium bandwidth data, wide band data, such as video information, must be circuit switched. In order to provide the new types of data and voice services that have been proposed, it is desirable to have a switching system that can provide both packet and circuit switching.
Another problem with the existence of only one unique route is the effect of unbalanced traffic conditions on the network. The problems due to unbalanced traffic are a result of the architecture of the basic banyan switching network. From FIG. 1, it can be seen that the network architecture is such that the first stage of the network is responsive to the address information to direct the packet to one-half of the network, sections 2 and 3, and that the second stage of network then directs the packet to sections 4 through 7 of the third stage with each of these sections representing a quarter of the network. The fourth, fifth, and sixth stages are responsive to the packet from the third stage to properly route the packet to the proper output conductor. Under certain unbalanced traffic conditions, the basic architecture of the banyan switching network results in concentrations of packets in certain nodes in the third stage.
The following example illustrates the effect of unbalanced traffic conditions in the third stage. Consider the example where packets from conductors 200-0, 200-1, 200-16, 200-17, 200-32, 200-33, 200-48, and 200-49 are transferring packets to conductors 206-0 through 206-7. All packets from these input conductors must be switched through node 102-0 via the following paths. The communication path from 200-0 and 200-1 to output conductors 206-1 through 206-7 is through node 102-0 of stage 3 via the path of links 201-0 and 202-0; a path from input conductors 200-16 and 200-17 to output conductors 206-1 and 206-7 is via links 201-16 and 202-16 via node 102-0; the path from input conductors 200-32 and 200-33 to output conductors 206-1 through 206-7 is via links 201-32 and 202-0 through node 102-0; and similarly the path from input conductor 200-48 and 200-49 t the output conductors is via link 201-48 and 202-16 via node 102-0. The path from node 102-0 to the previously mentioned output conductors is via links 203-0, 204-0 or 204-1, 205-0 and 205-1, 205-4 or 205-5. It can be seen that the traffic capacity of the network for this example is limited to the traffic capacity of node 102-0.
In addition, if node 102-0 fails, there is no way to establish communication paths between the previously mentioned input conductors and the previously mentioned output conductors.
One known method for alleviating the reliability and traffic problems in a self-routing network is discussed in the report entitled, "Development of a Voice Funnel System", Bolt, Beranek and Newman, Inc., Report No. 4098, August, 1979, pages III-29 through III-76, which discloses the use of an extra stage of banyan switching nodes at the input of a self-routing network to resolve the previously mentioned problems of traffic unbalance and reliability. The report proposes that this extra stage of switching be identical to other stages of the network and be utilized by adding an extra bit of addressing to the address field of each packet being routed through the switching network. This extra stage of switching would precede stage 1 of FIG. 1. The extra address bit would be controlled by hardware or software external to the switching network and would determine the route through the switching network. The hardware or software would use this bit so as to avoid a node which was failing or experiencing heavy traffic.
Whereas the method proposed by the report allows the addition of more than one unique route through the switching network, it requires that an additional stage be added to the network and that the decision of which route to use be made external to the network. In addition, the network described in this report can only be used to switch packets.